On the minimum number of non-monochromatic simplices for Sperner labelings of a regular triangulation

L.A. Calvo, S. Merchán Rubira, D. Raboso Paniagua, J. Rodrigo, J.M. Rodríguez García

PLoS One Vol. 21, nº. 8, pp. e0356507

Summary:

Motivated by an open problem in the literature stated by Mirzakhani and Vondrák, we give a lower bound of the number of non-monochromatic simplices for Sperner labelings of the vertices of a triangulation of a given k-simplex with vertices of integer coordinates. This triangulation maximizes the number of simplices over all the triangulations of the k-simplex with vertices of integer coordinates.

Spanish layman's summary:

Este trabajo estudia el número mínimo de símplices no monocromáticos que aparecen en etiquetados de Sperner de una triangulación regular. Motivado por un problema abierto de Mirzakhani y Vondrák, establece cotas inferiores y superiores del mismo orden asintótico, caracterizando además la triangulación mediante herramientas de teoría de grafos y obteniendo resultados exactos en varios casos iniciales.

English layman's summary:

This work studies the minimum number of non-monochromatic simplices arising in Sperner labelings of a regular triangulation. Motivated by an open problem posed by Mirzakhani and Vondrák, it establishes lower and upper bounds of the same asymptotic order, also characterizing the triangulation through graph-theoretic tools and obtaining exact results in several initial cases.

Keywords: Sperner labeling; Hypergraph labeling problem; Discrete Optimization.

JCR-JIF Impact Factor and WoS quartile: 2,800 - Q2 (2025)

DOI reference: https://doi.org/10.1371/journal.pone.0356507

Published on paper: 2026.

Published on-line: August 2026.

Citation:
L.A. Calvo, S. Merchán Rubira, D. Raboso Paniagua, J. Rodrigo, J.M. Rodríguez García, "On the minimum number of non-monochromatic simplices for Sperner labelings of a regular triangulation", PLoS One, Vol. 21, nº. 8, pp. e0356507, 2026. [Online: August 2026] doi: 10.1371/journal.pone.0356507